package com.lxu.TreeDemo1;

import java.util.Arrays;

public class CreatTree {

    //中序遍历递归算法
    public static void inOrder(int[] tree,int j){
        if(j<16&&tree[j]!=0){
            inOrder(tree,j*2);
            System.out.print(tree[j]+",");
            inOrder(tree,j*2+1);
        }
    }

    //前序遍历递归算法
    public static void PreOrder(int[] tree,int j){
        if(j<16&&tree[j]!=0){
            System.out.print(tree[j]+",");
            PreOrder(tree,j*2);
            PreOrder(tree,j*2+1);
        }
    }

    //后序遍历递归算法
    public static void PostOrder(int[] tree,int j){
        if(j<16&&tree[j]!=0){
            PostOrder(tree,j*2);
            PostOrder(tree,j*2+1);
            System.out.print(tree[j]+",");
        }
    }

    //二叉树搜索
    public static void BinarySearch(int[] tree,int j,int value){
        if(j<16&&tree[j]!=0){
            if(tree[j]==value){
                System.out.println("查到："+tree[j]);
                return;
            }
            if (value>tree[j]){
                System.out.println("-----右");
                BinarySearch(tree,j*2+1,value);
            }
            if (value<tree[j]){
                System.out.println("左");
                BinarySearch(tree,j*2,value);
            }
        }
    }

    //数组存储二叉树，按照二叉排序树构建
    public static void main(String[] args) {
        int i, level;
        int[] data = {6, 3, 5, 9, 7, 8, 4, 2};
        int[] btree = new int[16];

        for (i = 0; i < 8; i++) {
            for (level = 1; btree[level] != 0; ) {
                if (data[i] > btree[level])
                    level = level * 2 + 1;//右子树
                else
                    level = level * 2;//左子树
            }
            btree[level] = data[i];
        }
        BinarySearch(btree,1,4);
        System.out.println("二叉树内容"+Arrays.toString(btree));

        int[] a={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        System.out.println("前");
        PreOrder(btree,1);
        System.out.println("中");
        inOrder(btree,1);
        System.out.println("后");
        PostOrder(btree,1);

    }


}
